In continuously operating, real-time systems, deallocation of system resources is an area where minor errors have major consequences. If errors occur in resource deallocation, or the system gets into an unusual state, resources are lost to processing and to the users of the system. Lost resources can cause delays, and in some cases, lead to system failure. Under current practice, the system programmer must carefully and thoroughly design and implement deallocation of resources such as memory, peripheral devices and, in electronic telephone switching systems, lines, ports, service circuits and the like.
These programming practices are complex and prior art solutions to this problem are inadequate. In procedural program-controlled systems, audits are used to recover lost resources. Audits, however, are themselves complex to design and to implement properly, and require a substantial amount of system real-time to carry out their function. Further, audits have not yet been designed that can effectively handle all possible situations that may be encountered in a continuously operating system. Initialization of part or all of the system is the only alternative in some cases, which can have severe impact on a switching system or other systems requiring long-term reliability.
Object-oriented program-controlled systems have been proposed as an alternative to procedural program-controlled systems because, by their very nature, they increase productivity of programmers and because some object-oriented program-controlled systems include a form of automatic resource deallocation. As will be discussed in more detail below, these systems have not yet addressed the problems of recovering resources at a rate proportionate to the rate of allocation and do not run without blocking all other processing of the system for significant and unpredictable periods of time. To understand these problems, an understanding of object-oriented programming systems is necessary.
An object-oriented program-controlled system, at its basic level, is concerned with objects, messages and the interaction between the two. Processing in these systems is defined as sending messages to objects. Objects generally comprise data used by the system and messages generally comprise operations to be performed on an object's data. Objects are long-lived (as compared to messages) and require space in memory, which is allocated at the time of creation of the objects. Object-oriented program-controlled systems create objects frequently, for each new or different functionality required by processing. Therefore, as in procedural program systems, memory space is a resource that must be recycled carefully so that memory resources do not become totally exhausted, making further processing impossible.
When the data that an object represents is no longer useful, its resources may be discarded, and the memory for storing that data may be reallocated. Data in an object may include references to other objects to which messages may be sent as part of processing. A message may stimulate an object to add, delete or change a reference to another object. When all references to an object or group of objects are deleted, these objects become "unreachable," and hence the object or objects are no longer useful, and the memory resources for storing that object or objects should be recovered.
It is the nature of objects that there is a limit to the number of references that they may have at any given time. Operations on objects cause new objects to be created. As a result, references to previously used objects are normally deleted as the functionality of a prior object is no longer needed; this makes available the space for references to objects, which space may be reused for the new objects. An object becomes unreachable when all of the referencing objects delete all references to that object. The reference storage space of unreachable objects can be reused to reference other objects.
Several object-oriented program-controlled systems utilize a form of automatic storage management called "garbage collectors," to recover memory resources. Generically, garbage collectors identify unreachable objects and return resources associated with identified unreachable objects to a pool of available resources. Most garbage collectors also include a form of memory compaction, which moves reachable objects so that they are substantially contiguous in memory. A problem in the art is that most garbage collectors stop all other activity of the object-oriented programming system for a significant, unpredictable duration of time while the garbage collector is running, which makes them unsuitable for systems with real-time constraints.
A common garbage collector that stops all other activity while it is running is the mark/sweep garbage collector. In mark/sweep garbage collectors, the "mark" phase uses a set of root objects as a basis for a recursive traversal of the graph of objects referenced directly or indirectly by the root objects, marking all objects reachable from the root set. In the "sweep" phase, all objects are sequentially examined. Objects that are not marked are deleted and objects that are marked are unmarked and saved. Obviously, the time required for the mark/sweep garbage collector to complete its task is at least proportional to the size of the system. For systems with real-time constraints, the uncontrolled time delay while the garbage collector runs is unacceptable.
In response to the need for a non-disruptive garbage collector, C. Hewitt and H. Lieberman proposed a garbage collector for an object-oriented program-controlled system in Hewitt/Lieberman, "A Real Time Garbage Collector That Can Recover Temporary Storage Quickly," MIT Artificial Intelligence Laboratories, A. I. Memo No. 569, April, 1980, which, to our knowledge, has never been implemented. This relatively more sophisticated garbage collector is based on two statistical observations: 1. recently created objects are more likely to become unreachable than older objects, and 2. objects mostly reference contemporary or prior-created objects. In order to take advantage of these two observations, Hewitt/Lieberman group objects into "generations" according to time of creation of the object. Each generation has a predetermined storage size; therefore, the number of objects in a generation may vary. Identification of unreachable objects is focused on the most recently created generations, since, according to observation 1, these generations contain objects that are most likely to become unreachable. This garbage collector selects a "condemned generation" and causes the condemned generation and all generations younger than this generation to form a "condemned region." By focusing on objects within a condemned region and not on all objects, this garbage collector is more efficient (i.e., recovers more memory per unit of processing time) than basic mark/sweep garbage collectors.
Observation two provides an additional efficiency in the Hewitt/Lieberman garbage collector over mark/sweep garbage collectors. Because objects mostly reference contemporary or prior-created objects, the number of references to an object in one generation from a prior generation is generally not large. Thus, it is practical to keep a list of such references from a prior generation associated with each generation. Traversing this list sufficiently identifies all object references from older generations into generations in the condemned region. Therefore, by using this list, this garbage collector avoids searching generations older than the condemned region for references into the condemned region. Thus, the Hewitt/Lieberman garbage collector collects more unreachable objects per unit processing time than basic mark/sweep garbage collectors.
In the Hewitt/Lieberman garbage collector, the list of references to objects in a younger generation from objects in an older generation is called a "remembered set". A "remembered set" associated with a generation stores or "remembers" the "set" of references to objects in the associated generation from objects in older generations. During processing, references can be created through assignments. When assignment processing detects the creation of a reference to an object belonging to a younger generation from an object in an older generation, the reference assignment is "trapped", and data regarding the older object is recorded in the remembered set data structure of the generation to which the referenced object belongs. According to observation 2, these traps occur infrequently, so that the overhead incurred by the trap is gained back in the efficiency of the garbage collector. By using a remembered set of references from older objects, the garbage collector is simplified because the effort needed to search older objects for references to younger objects is greatly reduced.
An area not addressed by Hewitt/Lieberman is one of the primary causes of time delay in garbage collectors: the marking and sweeping of objects referenced from stacks. Processing of the system must stop for the marking of objects referenced from each stack because a reference to an object from a stack can move, undetected by the garbage collector, if the system is allowed to run while the stacks are being checked for references. For example, consider an object referenced from the bottom of a stack, wherein stacks are swept from the top down. The referenced object would not be marked (and therefore considered to be unreachable) at the start of the stack sweep. If the stack were swept to a point before the reference to the object and then the system permitted to run, the reference to the object could move to a part of the stack that had already been swept. As a result, the referenced object would not be marked, and, during the sweep phase, the referenced object would be falsely recovered, i.e., freed for reallocation. Recovering a referenced object could potentially cause system malfunction. Therefore, a problem in the art is that, even in relatively efficient garbage collectors, (such as the Hewitt/Lieberman system) stacks cannot be checked for object references without locking out other processing.
Even with its efficiencies, the proposed Hewitt/Lieberman garbage collector is not a complete solution for the needs of a program-controlled real-time operating system. The condemned region is still searched in the above-discussed mark/sweep fashion using an unpredictable amount of real time. No mechanism is discussed by Hewitt/Lieberman to control the rate at which garbage collection progresses. In real-time systems, these are significant problems, which could result in degradation of system performance.
A further problem in the art is that current garbage collectors, including Hewitt/Lieberman, often compact storage as part of the identification of reachable objects. In systems where the number and kind of objects do not change greatly, frequent compaction is an unnecessary real-time expense. Compaction in such systems is required much less often. This is especially true for applications in, for example, electronic telephone switching systems, where a limited number of classes of objects are used, but a large number are created and discarded during typical call processing.
A problem in the art, therefore, is that there is no garbage collector satisfactory for use in real-time object-oriented program-controlled systems.